home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / var / lib / python-support / python2.6 / gdata / Crypto / Protocol / Chaffing.pyc (.txt) < prev   
Encoding:
Python Compiled Bytecode  |  2009-04-20  |  8.6 KB  |  197 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyc (Python 2.6)
  3.  
  4. '''This file implements the chaffing algorithm.
  5.  
  6. Winnowing and chaffing is a technique for enhancing privacy without requiring
  7. strong encryption.  In short, the technique takes a set of authenticated
  8. message blocks (the wheat) and adds a number of chaff blocks which have
  9. randomly chosen data and MAC fields.  This means that to an adversary, the
  10. chaff blocks look as valid as the wheat blocks, and so the authentication
  11. would have to be performed on every block.  By tailoring the number of chaff
  12. blocks added to the message, the sender can make breaking the message
  13. computationally infeasible.  There are many other interesting properties of
  14. the winnow/chaff technique.
  15.  
  16. For example, say Alice is sending a message to Bob.  She packetizes the
  17. message and performs an all-or-nothing transformation on the packets.  Then
  18. she authenticates each packet with a message authentication code (MAC).  The
  19. MAC is a hash of the data packet, and there is a secret key which she must
  20. share with Bob (key distribution is an exercise left to the reader).  She then
  21. adds a serial number to each packet, and sends the packets to Bob.
  22.  
  23. Bob receives the packets, and using the shared secret authentication key,
  24. authenticates the MACs for each packet.  Those packets that have bad MACs are
  25. simply discarded.  The remainder are sorted by serial number, and passed
  26. through the reverse all-or-nothing transform.  The transform means that an
  27. eavesdropper (say Eve) must acquire all the packets before any of the data can
  28. be read.  If even one packet is missing, the data is useless.
  29.  
  30. There\'s one twist: by adding chaff packets, Alice and Bob can make Eve\'s job
  31. much harder, since Eve now has to break the shared secret key, or try every
  32. combination of wheat and chaff packet to read any of the message.  The cool
  33. thing is that Bob doesn\'t need to add any additional code; the chaff packets
  34. are already filtered out because their MACs don\'t match (in all likelihood --
  35. since the data and MACs for the chaff packets are randomly chosen it is
  36. possible, but very unlikely that a chaff MAC will match the chaff data).  And
  37. Alice need not even be the party adding the chaff!  She could be completely
  38. unaware that a third party, say Charles, is adding chaff packets to her
  39. messages as they are transmitted.
  40.  
  41. For more information on winnowing and chaffing see this paper:
  42.  
  43. Ronald L. Rivest, "Chaffing and Winnowing: Confidentiality without Encryption"
  44. http://theory.lcs.mit.edu/~rivest/chaffing.txt
  45.  
  46. '''
  47. __revision__ = '$Id: Chaffing.py,v 1.7 2003/02/28 15:23:21 akuchling Exp $'
  48. from Crypto.Util.number import bytes_to_long
  49.  
  50. class Chaff:
  51.     '''Class implementing the chaff adding algorithm.
  52.  
  53.     Methods for subclasses:
  54.  
  55.             _randnum(size):
  56.                 Returns a randomly generated number with a byte-length equal
  57.                 to size.  Subclasses can use this to implement better random
  58.                 data and MAC generating algorithms.  The default algorithm is
  59.                 probably not very cryptographically secure.  It is most
  60.                 important that the chaff data does not contain any patterns
  61.                 that can be used to discern it from wheat data without running
  62.                 the MAC.
  63.  
  64.     '''
  65.     
  66.     def __init__(self, factor = 1, blocksper = 1):
  67.         '''Chaff(factor:float, blocksper:int)
  68.  
  69.         factor is the number of message blocks to add chaff to,
  70.         expressed as a percentage between 0.0 and 1.0.  blocksper is
  71.         the number of chaff blocks to include for each block being
  72.         chaffed.  Thus the defaults add one chaff block to every
  73.         message block.  By changing the defaults, you can adjust how
  74.         computationally difficult it could be for an adversary to
  75.         brute-force crack the message.  The difficulty is expressed
  76.         as:
  77.  
  78.             pow(blocksper, int(factor * number-of-blocks))
  79.  
  80.         For ease of implementation, when factor < 1.0, only the first
  81.         int(factor*number-of-blocks) message blocks are chaffed.
  82.         '''
  83.         if factor <= factor:
  84.             pass
  85.         elif not factor <= 1:
  86.             raise ValueError, "'factor' must be between 0.0 and 1.0"
  87.         
  88.         if blocksper < 0:
  89.             raise ValueError, "'blocksper' must be zero or more"
  90.         blocksper < 0
  91.         self._Chaff__factor = factor
  92.         self._Chaff__blocksper = blocksper
  93.  
  94.     
  95.     def chaff(self, blocks):
  96.         """chaff( [(serial-number:int, data:string, MAC:string)] )
  97.         : [(int, string, string)]
  98.  
  99.         Add chaff to message blocks.  blocks is a list of 3-tuples of the
  100.         form (serial-number, data, MAC).
  101.  
  102.         Chaff is created by choosing a random number of the same
  103.         byte-length as data, and another random number of the same
  104.         byte-length as MAC.  The message block's serial number is
  105.         placed on the chaff block and all the packet's chaff blocks
  106.         are randomly interspersed with the single wheat block.  This
  107.         method then returns a list of 3-tuples of the same form.
  108.         Chaffed blocks will contain multiple instances of 3-tuples
  109.         with the same serial number, but the only way to figure out
  110.         which blocks are wheat and which are chaff is to perform the
  111.         MAC hash and compare values.
  112.         """
  113.         chaffedblocks = []
  114.         count = len(blocks) * self._Chaff__factor
  115.         blocksper = range(self._Chaff__blocksper)
  116.         for i, wheat in map(None, range(len(blocks)), blocks):
  117.             if i < count:
  118.                 (serial, data, mac) = wheat
  119.                 datasize = len(data)
  120.                 macsize = len(mac)
  121.                 addwheat = 1
  122.                 for j in blocksper:
  123.                     import sys
  124.                     chaffdata = self._randnum(datasize)
  125.                     chaffmac = self._randnum(macsize)
  126.                     chaff = (serial, chaffdata, chaffmac)
  127.                     if addwheat and bytes_to_long(self._randnum(16)) & 64:
  128.                         chaffedblocks.append(wheat)
  129.                         addwheat = 0
  130.                     
  131.                     chaffedblocks.append(chaff)
  132.                 
  133.                 if addwheat:
  134.                     chaffedblocks.append(wheat)
  135.                 
  136.             addwheat
  137.             chaffedblocks.append(wheat)
  138.         
  139.         return chaffedblocks
  140.  
  141.     
  142.     def _randnum(self, size):
  143.         randpool = randpool
  144.         import Crypto.Util
  145.         import time
  146.         pool = randpool.RandomPool(size * 2)
  147.         while size > pool.entropy:
  148.             pass
  149.         return pool.get_bytes(size)
  150.  
  151.  
  152. if __name__ == '__main__':
  153.     text = 'We hold these truths to be self-evident, that all men are created equal, that\nthey are endowed by their Creator with certain unalienable Rights, that among\nthese are Life, Liberty, and the pursuit of Happiness. That to secure these\nrights, Governments are instituted among Men, deriving their just powers from\nthe consent of the governed. That whenever any Form of Government becomes\ndestructive of these ends, it is the Right of the People to alter or to\nabolish it, and to institute new Government, laying its foundation on such\nprinciples and organizing its powers in such form, as to them shall seem most\nlikely to effect their Safety and Happiness.\n'
  154.     print 'Original text:\n=========='
  155.     print text
  156.     print '=========='
  157.     blocks = []
  158.     size = 40
  159.     for i in range(0, len(text), size):
  160.         blocks.append(text[i:i + size])
  161.     
  162.     print 'Calculating MACs...'
  163.     from Crypto.Hash import HMAC, SHA
  164.     key = 'Jefferson'
  165.     macs = [ HMAC.new(key, block, digestmod = SHA).digest() for block in blocks ]
  166.     if not len(blocks) == len(macs):
  167.         raise AssertionError
  168.     source = []
  169.     m = map(None, range(len(blocks)), blocks, macs)
  170.     print m
  171.     for i, data, mac in m:
  172.         source.append((i, data, mac))
  173.     
  174.     print 'Adding chaff...'
  175.     c = Chaff(factor = 0.5, blocksper = 2)
  176.     chaffed = c.chaff(source)
  177.     from base64 import encodestring
  178.     wheat = []
  179.     print 'chaffed message blocks:'
  180.     for i, data, mac in chaffed:
  181.         h = HMAC.new(key, data, digestmod = SHA)
  182.         pmac = h.digest()
  183.         if pmac == mac:
  184.             tag = '-->'
  185.             wheat.append(data)
  186.         else:
  187.             tag = '   '
  188.         print tag, '%3d' % i, repr(data), encodestring(mac)[:-1]
  189.     
  190.     print 'Undigesting wheat...'
  191.     newtext = ''.join(wheat)
  192.     if newtext == text:
  193.         print 'They match!'
  194.     else:
  195.         print 'They differ!'
  196.  
  197.